package com.example.demo.leetcode.top100;

import java.util.*;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _11滑动窗口最大值
 * @description
 * @date 2023/06/05 21:13
 * <p>
 * ******************************************************
 */
public class _11滑动窗口最大值 {

    LinkedList<Integer> maxq = new LinkedList<>();

    // 在队尾添加元素 n
    void push(int n) {
        while (!maxq.isEmpty() && maxq.peekLast() < n) {
            // 删除比当前值小的值,保证有序性
            maxq.pollLast();
        }
        maxq.addLast(n);
    }

    // 返回当前队列中的最大值
    int max() {
        return maxq.isEmpty() ? 0 : maxq.getFirst();
    }

    // 队头元素如果是 n，删除它
    void pop(int n) {
        if (!maxq.isEmpty() && maxq.peekFirst() == n)
            maxq.pollFirst();
    }


    public int[] maxSlidingWindow1(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        _11滑动窗口最大值 window = new _11滑动窗口最大值();
        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) {
                window.push(nums[i]);
            } else {
                window.push(nums[i]);
                res.add(window.max());
                window.pop(nums[i - k + 1]);
            }
        }
        int[] result = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }






    public int[] maxSlidingWindow(int[] nums, int k) {

        Queue<Integer> queue = new PriorityQueue<>( new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        List<Integer> result = new LinkedList<>();
        int left = 0;
        int right = 0;

        while (right < nums.length) {
            int curr = nums[right];
            queue.offer(curr);
            right++;

            if (queue.size() == k) {
                result.add(queue.peek());
                queue.remove(nums[left]);
                left++;
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}
